package cn.cxq.learning.map;

import org.junit.jupiter.api.Test;

import java.util.*;

public class LFU {

    @Test
    public void test() {
        System.out.println(Arrays.toString(LFU(new int[][]{{1,1,1},{1,2,2},{1,3,2},{1,2,4},{1,3,5},{2,2},{1,4,4},{2,1}}, 3)));

        System.out.println();
    }

    public int[] LFU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<>();

        HashMap<Integer, int[]> map = new HashMap<>(); // int[] 是一个长度为2的数组,第一个元素用来存储value，第二个元素用来存储访问次数

        for (int[] operator : operators) {
            if (operator[0] == 1) {
                if (!map.containsKey(operator[1])) {
                    // 如果size等于k, 就要删除一个元素
                    if (map.size() == k) {
                        ArrayList<Integer> rm = new ArrayList<>();
                        int min = Integer.MAX_VALUE;
                        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
                            if (min > entry.getValue()[1]) {
                                rm.clear();
                                rm.add(entry.getKey());
                                min = entry.getValue()[1];
                            } else {
                                if (entry.getKey() == min) {
                                    rm.add(entry.getKey());
                                }
                            }
                        }
                        for (Integer key : queue) {
                            if (rm.contains(key)) {
                                queue.remove(key);
                                map.remove(key);
                                break;
                            }
                        }
                    }
                    map.put(operator[1], new int[] {operator[2], 1});
                    queue.offerLast(operator[1]);
                } else {
                    map.put(operator[1], new int[] {operator[2], map.get(operator[1])[1] + 1});
                }
            } else {
                if (map.containsKey(operator[1])) {
                    list.add(map.get(operator[1])[0]);
                    map.get(operator[1])[1]++;
                } else {
                    list.add(-1);
                }
            }
        }

        int[] res = new int[list.size()];

        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }
}
